#include <iostream>
using namespace std;

int tmp[10] = {0};

void print(int arr[], int len);
void merge_sort(int arr[], int base, int top);
void merge(int arr[], int base, int top);

int main()
{
    int arr[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    int len = sizeof(arr) / sizeof(int);

    print(arr, len);
    merge_sort(arr, 0, 9);
    print(tmp, len);
    print(arr, len);
    return 0;
}

void print(int arr[], int len)
{
    for (int i = 0; i < len; ++i)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void merge_sort(int arr[], int base, int top)
{
    int mid = (base + top) / 2;
    if (base < top)
    {
        merge_sort(arr, base, mid);
        merge_sort(arr, mid + 1, top);
        merge(arr,base,top);
    }
}

void merge(int arr[], int base, int top)
{
    int mid = (base + top) / 2;
    int i = base , j = base , k = mid + 1;
    while(j <= mid && k <= top)
    {
        if(arr[j] <= arr[k])
        {
            tmp[i++] = arr[j++];
        }
        else
        {
            tmp[i++] = arr[k++]; 
        }
    }
    while(j <= mid) tmp[i++] = arr[j++];
    while(k <= top) tmp[i++] = arr[k++];
    for(int x = base; x <= top; x++) arr[x] = tmp[x]; // 这一步非常重要

}
